#include "RLE.h"

unsigned int
RLE::Encode_MN5(const unsigned char * /*[in]*/data, unsigned int /*[in]*/bytes, unsigned char * /*[out]*/encoded, unsigned int & /*[out]*/enc_bytes)
{
    // RLE (MN5 variation of length 4) encoding
    //  - example: "AAAAAAABBBBCCCD" -->  "AAAA\3BBBB\0CCCD"
    enc_bytes = 0;
    unsigned char c, n;
    int reps = 0;
    if(bytes > 0)
    {
        c = encoded[enc_bytes++] = data[0];
        for(unsigned int i = 1; i < bytes; i++)
        {
            if(data[i] == c)
            {
                ++reps;
                if(reps <= 4)
                    encoded[enc_bytes++] = c;
                else
                {
                    if(reps > 255)	// == 256
                    {
                        n = reps - 4 - 1;
                        encoded[enc_bytes++] = n;
                        encoded[enc_bytes++] = c;
                        reps = 1;
                    }
                }
            }
            else
            {
                if(reps >= 4)
                {
                    n = reps - 4;
                    encoded[enc_bytes++] = n;
                }
                reps = 1;
                c = data[i];
                encoded[enc_bytes++] = c;
            }
                
        }
    }
    if(reps >= 4) encoded[enc_bytes++] = unsigned char(reps - 4);
    //
    return enc_bytes;
}

unsigned int
RLE::Decode_MN5(const unsigned char * /*[in]*/data, unsigned int /*[in]*/bytes, unsigned char * /*[out]*/decoded, unsigned int & /*[out]*/dec_bytes)
{
    // RLE (MN5 variation of length 4) decoding
    //  - example: "AAAA\3BBBB\0CCCD" --> "AAAAAAABBBBCCCD"
    dec_bytes = 0;
    unsigned char c;
    int reps = 1;
    if(bytes > 0)
    {
        c = decoded[dec_bytes++] = data[0];
        for(unsigned int i = 1; i < bytes; i++)
        {
            // next character is a number of repetitions
            if(reps == 4)
            {
                for(int r = data[i]; r > 0; r--)
                    decoded[dec_bytes++] = c;
                reps = 1;
                if((++i) < bytes)
                    decoded[dec_bytes++] = c = data[i];
                continue;
            }
            // a character
            if(data[i] == c)
                ++reps;
            else
            {
                reps = 1;
                c = data[i];
            }
            decoded[dec_bytes++] = c;
        }
    }
    //
    return dec_bytes;
}

// -------------------------------------------------------------------
#define RUNA 0x100
#define RUNB 0x200
#define WRITE_RUNA_RUNB_SEQUENCE()                                   \
    if(write)                                                        \
    {                                                                \
        if(reps > 0)                                                 \
            --reps;                                                  \
        else                                                         \
            reps = (1ULL << (--bits)) - 1;                           \
                                                                     \
        for(int b = 0; b < bits; b++)                                \
        {                                                            \
            if(reps % 2 == 1) encoded[enc_len++] = RUNB;             \
            else              encoded[enc_len++] = RUNA;             \
            reps >>= 1;                                              \
        }                                                            \
        bits = 0;                                                    \
        write = false;                                               \
    }
// -------------------------------------------------------------------

unsigned int
RLE::Encode_AB(const unsigned char * /*[in]*/data, unsigned int /*[in]*/bytes, unsigned short * /*[out]*/encoded, unsigned int & /*[out]*/enc_len)
{
    // ------------------------------------------------------------------
    // RLE (RUNA,RUNB variation) encoding
    // RUNA --> +
    // RUNB --> *2
    // ------------------------------------------------------------------
    // RUNA RUNB RUNA RUNA RUNB (ABAAB)
    //   1    2    4    8   16       <-- position_index^2
    //   1    4    4    8   32 = 49  <-- code (number of repetitions)
    // ------------------------------------------------------------------
    //  - example: (0,0,0,0,0,1) --> 0,RUNB,RUNA,1
    // ------------------------------------------------------------------
    // main idea of the algorithm:
    // bits = floor(log2(number_of_repetitions))
    // code = number_of_repetitions - (2^bits - 1)
    // -- then write the `code` as binary number by `bits` bits
    //    -- then 1 is RUNB and 0 is RUNA
    // ------------------------------------------------------------------
    // the following code is computing the code without
    // use of the log2() => it should be faster
    // theoretical computional complexity is O(n + log2(n)/2) = O(n),
    // where n is number of bytes read from the file,
    // therefore it's linear linear complexity
    // - explanation:
    // -- n: all bytes must be read
    // -- log2(n): if all the bytes are the same size then
    //             number of repetitions can be written as log2(n) bits
    // ----> log2(n)/2: x-bit value in binary can be written as (x/2)-bit
    //                  value in RUNA/RUNB encoding
    // ------------------------------------------------------------------
    bool write;
    unsigned char bits;
    unsigned short c;
    unsigned long long limit;
    unsigned int reps = 0, pos;
    enc_len = 0;
    // encode
    if(bytes > 0)
    {
        pos = 0;
        bits = 0;
        write = false;
        c = encoded[enc_len++] = data[pos++];
        while(pos < bytes)	// this is loop where sequence of RUNA/RUNB is computated
        {
            reps = 0;	// this is here on purpose - start from the zero, but with more bits!
            ++bits;	// how many RUNA/RUNB symbols is needed to write the number of repetitions
            limit = (1ULL << bits);	// how many values can be expressed by x bits
            for(unsigned int i = 0; (i < limit) && (pos < bytes); i++, pos++)
            {
                if(data[pos] == c)
                {
                    ++reps;
                    write = true;
                }
                else
                {
                    WRITE_RUNA_RUNB_SEQUENCE();
                    c = encoded[enc_len++] = data[pos++];
                    bits = 0;
                    break;
                }
            }
        }
        WRITE_RUNA_RUNB_SEQUENCE();
    }
    return enc_len;
}

unsigned int
RLE::Decode_AB(const unsigned short * /*[in]*/data, unsigned int /*[in]*/len, unsigned char * /*[out]*/decoded, unsigned int & /*[out]*/dec_bytes)
{
    // ------------------------------------------------------------------
    // RLE (RUNA,RUNB variation) decoding
    // RUNA --> +
    // RUNB --> *2
    // ------------------------------------------------------------------
    // RUNA RUNB RUNA RUNA RUNB (ABAAB)
    //   1    2    4    8   16       <-- position_index^2
    //   1    4    4    8   32 = 49  <-- code (number of repetitions)
    // ------------------------------------------------------------------
    //  - example: 0,RUNB,RUNA,1 --> (0,0,0,0,0,1)
    // ------------------------------------------------------------------
    unsigned char c;
    unsigned long long pos_val;
    dec_bytes = 0;
    // decode
    if(len > 0)
    {
        c = decoded[dec_bytes++] = (unsigned char)data[0];
        pos_val = 1;
        for(unsigned int i = 1; i < len; i++)
        {
            if(data[i] == RUNA)
            {
                for(unsigned long long r = pos_val; r > 0; r--)
                    decoded[dec_bytes++] = c;
                pos_val *= 2;
            }
            else if(data[i] == RUNB)
            {
                pos_val *= 2;
                for(unsigned long long r = pos_val; r > 0; r--)
                    decoded[dec_bytes++] = c;
            }
            else
            {
                c = decoded[dec_bytes++] = (unsigned char)data[i];
                pos_val = 1;
            }
        }
    }
    return dec_bytes;
}